#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,m,k,r,ans,a[N][N],ans1,vis[N];
struct node{
	int l,r;
}b[N],c[N];
vector<int>qq[N];
void bfs(int i)
{
	deque<node>q;
	q.push_front((node){0,c[i].l});
	while(!q.empty())
	{
		int nd=q.front().r,nz=q.front().l;
		q.pop_front();
		if(vis[nd]) continue;
		vis[nd]=1;
		if(nd==c[i].r)
		{
			ans+=nz;
			return;
		}
		for(int j=0;j<qq[nd].size();++j)
		{
			if(!vis[qq[nd][j]])
				if(a[nd][qq[nd][j]])
					q.push_back((node){nz+1,qq[nd][j]});
				else
					q.push_front((node){nz,qq[nd][j]});
		}
	}
}
int main()
{
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k>>r;
	for(int i=1;i<=m;++i)
		cin>>b[i].l>>b[i].r,qq[b[i].l].push_back(b[i].r),qq[b[i].r].push_back(b[i].l);
	for(int i=1;i<=k;++i)
		cin>>c[i].l>>c[i].r;
	for(int i=1;i<=m;++i)
		for(int j=1;j<=m;++j)
		{
			if(i!=j)
			{
				a[b[i].l][b[i].r]=a[b[i].r][b[i].l]=1;
				a[b[j].l][b[j].r]=a[b[j].r][b[j].l]=1;
				for(int z=1;z<=k;++z)
				{
					bfs(z);
					for(int zz=1;zz<=n;++zz)
						vis[zz]=0;
				}
				ans1=max(ans,ans1);
				ans=0;
				a[b[i].l][b[i].r]=a[b[i].r][b[i].l]=0;
				a[b[j].l][b[j].r]=a[b[j].r][b[j].l]=0;
			}
		}
	cout<<ans1;
	return 0;
 } 
